`
https://leetcode.cn/problems/coin-change/
`

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
  // dp[i] 表示凑成总金额 i 所需的最少硬币个数
  const dp = new Array(amount + 1).fill(Infinity)

  // 取 0 个硬币凑成总金额 0
  dp[0] = 0

  // 遍历 0 - amount 的金额
  for (let i = 0; i < dp.length; i++) {
    // 遍历所有可以使用的硬币
    for (const coin of coins) {
      // 如果 i - coin 小于 0，说明凑不出来，跳过
      if (i - coin < 0) continue
      // 比较凑成总金额 i 所需的最少硬币个数
      dp[i] = Math.min(dp[i], 1 + dp[i - coin])
    }
  }

  // 如果 dp[amount] 仍然是 Infinity，说明凑不出来，返回 -1
  return dp[amount] === Infinity ? -1 : dp[amount]
};

console.log(coinChange([1, 2, 5], 11))